// Copyright 2012 dmitry.a.novikov@gmail.com
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
// http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "consistenz.h"
#include "charindex.h"
#include <string.h>

namespace CnsZ {

  class CharCompare {
  public:
    bool operator()(const CharIndex::Node* op1, const wchar_t* op2) {
      return ::wcsncmp(op1->key, op2, 1)<0;
    }
    bool operator()(const wchar_t* op1, const CharIndex::Node* op2) {
      return ::wcsncmp(op1, op2->key, 1)<0;
    }
    bool operator()(const CharIndex::Node* op1, const CharIndex::Node* op2) {
      return ::wcsncmp(op1->key, op2->key, 1)<0;
    }
    static CharCompare cmp;
  };

  CharIndex::NodePtrArray::iterator CharIndex::NodePtrArray::lookup(const wchar_t* key) {
    return std::lower_bound(begin(), end(), key, CharCompare::cmp);
  }

  CharIndex::NodePtrArray::const_iterator CharIndex::NodePtrArray::lookup(const wchar_t* key) const {
    return std::lower_bound(begin(), end(), key, CharCompare::cmp);
  }

  void CharIndex::add(Object* item, const wchar_t* key, size_t keychars) {
    NodePtrArray* cur = &root;
    if(keychars == -1) {
      keychars = ::wcslen(key);
    }
    for(;;) {
      NodePtrArray::iterator pnode = cur->lookup(key);
      if(pnode!=cur->end() && !CharCompare::cmp(key, *pnode)) {
        if(keychars==1) {
          cur->insert(pnode, Node::New(item, key, keychars));
          return;
        }

        Node* node = *pnode;
        if(node->numchars>1) { // single leaf key branch
          node->add(item, key, keychars);
          return;
        }

        Object* obj = node->item.get();
        if(obj->isA()==Array<Node*, T>::classInfo()) { // branches
          cur = (NodePtrArray*)&node->item;
          ++key;
          --keychars;
        }
        else { // single leaf key branch
          node->add(item, key, keychars);
          return;
        }
      }
      else {
        cur->insert(pnode, Node::New(item, key, keychars));
        break;
      }
    }
  }

  P<Object> CharIndex::get(const wchar_t* key) const {
    const NodePtrArray* cur = &root;
    for(;;) {
      NodePtrArray::const_iterator pnode = cur->lookup(key);
      if(pnode!=cur->end() && !CharCompare::cmp(key, *pnode)) {
        Node* node = *pnode;
        if(node->numchars>1) { // single leaf key branch
          return node->item;
        }

        Object* obj = node->item.get();
        if(obj->isA()==Array<Node*, T>::classInfo()) { // branches
          cur = (NodePtrArray*)&node->item;
          ++key;
        }
        else { // single leaf key branch
          return node->item;
        }
      }
      else {
        break;
      }
    }
    return P<Object>();
  }


}//namespace CnsZ
